#include <iostream>
#include <queue>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x)
        :val(x)
        ,left(nullptr)
        ,right(nullptr)
    {}
    TreeNode(int x, TreeNode* l, TreeNode* r)
        :val(x)
        ,left(l)
       ,right(r)
    {}
};

class Solution 
{
public:
    bool isCompleteTree(TreeNode* root) 
    {
        if (!root)
            return true;

        queue<TreeNode*> q;
        q.push(root);
        bool flag = false;
        while (!q.empty())
        {
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                if (!cur)
                    flag = true;
                else
                {
                    if (flag)
                        return false;
                    q.push(cur->left);
                    q.push(cur->right);
                }   
            }
        }
        return true;
    }
};

int main()
{
    //{1,2,3,4,5,#,6}
    TreeNode* E = new TreeNode(6);
    TreeNode* D = new TreeNode(5);
    TreeNode* C = new TreeNode(4);
    TreeNode* B = new TreeNode(3, nullptr, E);
    TreeNode* A = new TreeNode(2, C, D);
    TreeNode* root = new TreeNode(1, A, B);

    Solution xz;
    int n = xz.isCompleteTree(root);
    cout << n << endl;

	return 0;
}